package com.wyw.leetcode.learning.simple;

/**
 * leetcode topic 53
 * 最大子序和
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/10/29 10:09
 */
public class Topic053 {

    public static void main(String[] args) {
        int[] nums = {-2,-3,-1,-5};
//        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
//        int[] nums = {3,-2,-3,-3,1,3,0};
        System.out.println(maxSubArray(nums));
//        Test test = new Test();
//        System.out.println(test.maxSubArray(nums));
    }

    //动态规划算法
//    public static int maxSubArray(int[] nums) {
//        int pre = 0, maxAns = nums[0];
//        for (int x : nums) {
//            //pre来维护对于当前f(i)的f(i−1)的值是多少
//            pre = Math.max(pre + x, x);//判断f(i-1)是否要加到当前数上
//            maxAns = Math.max(maxAns, pre);//获取最大值
//        }
//        return maxAns;
//
//    }

    //贪心算法
    public static int maxSubArray(int[] nums) {
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int result = Integer.MIN_VALUE;
        int numsSize = nums.length;
        int sum = 0;
        for (int i = 0; i < numsSize; i++){
            sum += nums[i];
            result = Math.max(result, sum);
            //如果sum < 0,重新开始找子序串
            if (sum < 0){
                sum = 0;
            }
        }

        return result;

    }

    // 分治算法
    public int maxSubArray2(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return max3(maxSubArraySum(nums, left, mid),
                maxSubArraySum(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }

}
